package lanqiao._02算法训练.page02;

import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 问题描述
 * 　　24点游戏是一个非常有意思的游戏，很流行，玩法很简单：给你4张牌，每张牌上有数字（其中A代表1，J代表11，Q代表12，K代表13），你可以利用数学中的加、减、乘、除以及括号想办法得到24，例如：
 * 　　((A*K)-J)*Q等价于((1*13)-11)*12=24
 * 　　加减乘不用多说了，但除法必须满足能整除才能除！这样有一些是得不到24点的，所以这里只要求求出不超过24的最大值。
 * 输入格式
 * 　　输入第一行N(1<=N<=5)表示有N组测试数据。每组测试数据输入4行，每行一个整数(1到13)表示牌值。
 * 输出格式
 * 　　每组测试数据输出一个整数，表示所能得到的最大的不超过24的值。
 * 样例输入
 * 3
 * 3
 * 3
 * 3
 * 3
 * 1
 * 1
 * 1
 * 1
 * 12
 * 5
 * 13
 * 1
 * 样例输出
 * 24
 * 4
 * 21
 * 思路：
 * 深度搜索枚举所有情况，取不大于24中最大的
 * vis数组标记每个数是否操作过
 * 将4个数各作为一次基数，进行3次操作
 * 两种情况：
 * 1.将基数和其他未操作的数进行加减乘除
 * 2.选一个未操作的数和其他未操作的数进行加减乘除
 * @since 2022 - 10 - 31 - 0:02
 */
public class _12二十四点 {
}
class Main12{
    static int[] nums = new int[4];
    static boolean[] vis = new boolean[4];
    static int max = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        while(--n >= 0){
            for(int i = 0; i < 4; i++) vis[i] = false;
            for(int i = 0; i < 4; i++){
                nums[i] = sc.nextInt();
            }
            //记录每次dfs 不大于24 的 最大点数
            int res = Integer.MIN_VALUE;
            //将每个数各做一次基数
            for(int i = 0; i < 4; i++){
                vis[i] = true;
                max = 0;
                //操作3次
                dfs(3, nums[i]);
                res = Math.max(res, max);
                if(res == 24) break; //最大了
                vis[i] = false;
            }
            System.out.println(res);
        }
    }

    static void dfs(int cnt, int num){
        if(cnt == 0) {  //一种可能
            if(num <= 24){  //符合的结果
                max = Math.max(max, num);
            }
            return;
        }
        for(int i = 0; i < 4; i++){
            if(!vis[i]){
                vis[i] = true;
                //加当前数
                dfs(cnt - 1, num + nums[i]);
                //减当前数
                dfs(cnt - 1, num - nums[i]);
                //乘当前数
                dfs(cnt - 1, num * nums[i]);
                //除当前数
                if(nums[i] != 0 && num % nums[i] == 0)
                    dfs(cnt - 1, num / nums[i]);

                /*
                开始没有考虑以下情况
                部分用例通不过
                比如 1 1 1 10  输出 21 但最大的 (1 + 1) * (1 + 10) = 22
                num 与当前数 进行加减乘除是覆盖不到这种情况的
                 */
                //与其他没有操作的数进行加减乘除
                for(int j = 0; j < 4; j++){
                    if(!vis[j] && i != j){
                        int temp  = nums[j];
                        //减
                        nums[j] += nums[i];
                        dfs(cnt - 1, num);
                        nums[j]  = temp;    //回溯
                        //加
                        nums[j] -= nums[i];
                        dfs(cnt - 1, num);
                        nums[j]  = temp;    //回溯
                        //乘
                        nums[j] *= nums[i];
                        dfs(cnt - 1, num);
                        nums[j]  = temp;    //回溯
                        //除
                        if(nums[i] != 0 && nums[j] % nums[i] == 0){
                            nums[j] /= nums[i];
                            dfs(cnt - 1, num);
                            nums[j]  = temp;    //回溯
                        }
                    }
                }
                //回溯
                vis[i] = false;
            }
        }
    }
}
